package com.lihepeng.leecode.solid_aim_offer.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 * <p>
 *  
 * <p>
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 * <p>
 * 5
 * / \
 * 4   8
 * /   / \
 * 11  13  4
 * /  \    / \
 * 7    2  5   1
 * 返回:
 * <p>
 * [
 * [5,4,11,2],
 * [5,8,4,5]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution34 {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }

    private void recur(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        sum -= root.val;
        if (sum == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path));
        }
        recur(root.left, sum);
        recur(root.right, sum);
        path.removeLast();

    }

    /**
     * 2022年5月6日
     * 第二次刷题
     * @param root
     * @param expectNumber
     * @return
     */
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        if (root == null) {
            return result;
        }
        recuir(root,expectNumber);
        return result ;
    }

    /**
     * 迭代保存
     * @param root
     * @param expectNumber
     */
    ArrayList<Integer> arrayList = new ArrayList<>();
    private void recuir(TreeNode root,int expectNumber) {

        if (root ==null) {
            return;
        }
        arrayList.add(root.val);
        expectNumber -= root.val;
        if (root.left ==null && root.right ==null && expectNumber==0) {
            result.add(new ArrayList<>(arrayList));
        }
        recuir(root.left,expectNumber);
        recuir(root.right,expectNumber);

    }


    /**
     * 二叉树的先序遍历 通过递归方式来实现
     *
     * @return
     */
    public List<Integer> preOrder(TreeNode headNode) {
        List<Integer> res = new ArrayList<>();
        inorderTravel(res, headNode);
        return res;
    }

    private void inorderTravel(List<Integer> res, TreeNode cur) {
        res.add(cur.val);
        if (cur.left != null) {
            inorderTravel(res, cur.left);
        }
        if (cur.right != null) {
            inorderTravel(res, cur.right);
        }

    }

    @Test
    public void runTest() {
        TreeNode headNode = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        headNode.left = node1;
        headNode.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        List<Integer> integers = preOrder(headNode);
        System.out.println(integers);

    }
}
